use crate::cmp::{Cmp, MemtableKeyCmp};
use crate::rand::rngs::StdRng;
use crate::rand::{RngCore, SeedableRng};
use crate::types::LdbIterator;

use bytes::Bytes;
use std::cell::RefCell;
use std::cmp::Ordering;
use std::mem::{replace, size_of};
use std::rc::Rc;

/// 表示跳表中节点的最大层级（高度）为 12 层
///
/// 跳表的每个节点会随机生成一个高度（不超过这个最大值），不同节点可以有不同高度
///
/// 限制最大高度可以防止极端情况下某些节点高度过高导致的性能问题
///
/// 最大高度限制了跳表的最大可能层数
const MAX_HEIGHT: usize = 12;
/// 表示跳表的分支因子为 4
///
/// 分支因子用于计算节点高度的概率分布，通常节点高度为 h 的概率是 1/(branching_factor^h)
///
/// 这个值决定了跳表的 "稀疏程度"，分支因子为 4 意味着每提高一层，节点数量大约是下一层的 1/4
///
/// 分支因子决定了各层节点数量的分布规律
const BRANCHING_FACTOR: u32 = 4;

/// A node in a skipmap contains links to the next node and others that are further away (skips);
/// `skips[0]` is the immediate element after, that is, the element contained in `next`.
///
/// 这段代码定义了跳表（SkipMap）中的节点（Node）结构体，用于存储跳表中的数据以及节点之间的连接关系。
///
/// 跳表是一种多层链表结构，每个节点包含多个 "跳跃指针"，可以跨越多个节点直接访问更远的节点，从而实现高效的查找、插入和删除操作。
///
/// 这个Node结构体正是跳表这种特性的具体实现：
struct Node {
    /// 存储不同层级的跳跃指针数组，其中：
    ///
    /// skips[0] 对应最底层的跳跃指针，与 next 指向同一个节点（注释中特别说明）
    ///
    /// 更高索引的元素（如 skips[1]、skips[2] 等）指向更远的节点，形成更高层级的 "快捷通道"
    skips: Vec<Option<*mut Node>>,
    /// 指向链表中下一个节点的所有权指针，构成跳表的最底层（第 0 层）链表
    next: Option<Box<Node>>,
    /// 存储当前节点的键，Bytes 通常是一种高效的字节容器类型
    key: Bytes,
    /// 存储当前节点的值，Bytes 通常是一种高效的字节容器类型
    value: Bytes,
}

/// Implements the backing store for a `MemTable`. The important methods are `insert()` and
/// `contains()`; in order to get full key and value for an entry, use a `SkipMapIter` instance,
/// `seek()` to the key to look up (this is as fast as any lookup in a skip map), and then call
/// `current()`.
///
/// 这段代码定义了一个名为 InnerSkipMap 的结构体，它看起来是一个跳表（Skip List）的内部实现，用作 MemTable（内存表）的底层存储结构。
///
/// 功能用途：
///
/// 作为 MemTable 的后端存储
///
/// 提供 insert()（插入）和 contains()（包含检查）等核心方法
///
/// 通过 SkipMapIter 迭代器可以获取条目的完整键和值
///
/// 支持 seek() 操作来查找特定键，这是跳表中非常高效的查找方式
struct InnerSkipMap {
    /// 跳表的头节点（Box<Node> 表示一个堆分配的节点）
    head: Box<Node>,
    /// 随机数生成器（StdRng），跳表在插入时需要随机决定节点的层级
    rand: StdRng,
    /// 跳表中元素的数量
    len: usize,
    // approximation of memory used.
    /// 近似的内存使用量，用于跟踪这个数据结构消耗的内存
    approx_mem: usize,
    /// 比较器（Cmp 特征对象），用于定义键的比较方式，使跳表可以支持不同类型的键
    cmp: Rc<Box<dyn Cmp>>,
}

impl Drop for InnerSkipMap {
    // Avoid possible stack overflow caused by dropping many nodes.
    fn drop(&mut self) {
        let mut next_node = self.head.next.take();
        while let Some(mut boxed_node) = next_node {
            next_node = boxed_node.next.take();
        }
    }
}

pub struct SkipMap {
    map: Rc<RefCell<InnerSkipMap>>,
}

impl SkipMap {
    /// Returns a SkipMap that wraps the comparator inside a MemtableKeyCmp.
    pub fn new_memtable_map(cmp: Rc<Box<dyn Cmp>>) -> SkipMap {
        SkipMap::new(Rc::new(Box::new(MemtableKeyCmp(cmp))))
    }

    /// Returns a SkipMap that uses the specified comparator.
    pub fn new(cmp: Rc<Box<dyn Cmp>>) -> SkipMap {
        let mut s = Vec::new();
        s.resize(MAX_HEIGHT, None);

        SkipMap {
            map: Rc::new(RefCell::new(InnerSkipMap {
                head: Box::new(Node {
                    skips: s,
                    next: None,
                    key: Bytes::new(),
                    value: Bytes::new(),
                }),
                rand: StdRng::seed_from_u64(0xdeadbeef),
                len: 0,
                approx_mem: size_of::<Self>() + MAX_HEIGHT * size_of::<Option<*mut Node>>(),
                cmp,
            })),
        }
    }

    pub fn len(&self) -> usize {
        self.map.borrow().len
    }

    #[must_use]
    pub fn is_empty(&self) -> bool {
        self.len() == 0
    }

    /// 这段代码定义了一个名为 approx_memory 的公共方法，其功能是返回当前数据结构 跳表 所使用的近似内存量（以字节为单位）。
    pub fn approx_memory(&self) -> usize {
        self.map.borrow().approx_mem
    }

    pub fn contains(&self, key: &[u8]) -> bool {
        self.map.borrow().contains(key)
    }

    /// inserts a key into the table. key may not be empty.
    pub fn insert(&mut self, key: Vec<u8>, val: Vec<u8>) {
        assert!(!key.is_empty());
        self.map.borrow_mut().insert(key, val);
    }

    /// 这段代码定义了一个名为 iter 的公共方法，用于创建并返回跳表（SkipMap）的迭代器 SkipMapIter。
    ///
    /// 具体分析其功能：
    ///
    /// 该方法属于 SkipMap 结构体（从 self.map 可以推断），调用后会生成一个迭代器实例
    ///
    /// 迭代器的初始化包含两个部分：
    ///
    /// map: self.map.clone()：通过克隆 Rc<RefCell<InnerSkipMap>> 引用，让迭代器共享对跳表内部数据的访问权
    ///
    /// current: self.map.borrow().head.as_ref() as *const Node：将迭代器的起始位置设置为跳表的头节点（head），通过原始指针指向头节点，作为迭代的起点
    pub fn iter(&self) -> SkipMapIter {
        SkipMapIter {
            map: self.map.clone(),
            current: self.map.borrow().head.as_ref() as *const Node,
        }
    }
}

impl InnerSkipMap {
    fn random_height(&mut self) -> usize {
        let mut height = 1;

        while height < MAX_HEIGHT && self.rand.next_u32() % BRANCHING_FACTOR == 0 {
            height += 1;
        }

        height
    }

    fn contains(&self, key: &[u8]) -> bool {
        if let Some(n) = self.get_greater_or_equal(key) {
            n.key.starts_with(key)
        } else {
            false
        }
    }

    /// Returns the node with key or the next greater one
    /// Returns None if the given key lies past the greatest key in the table.
    ///
    /// 这段代码定义了跳表（InnerSkipMap）中的 get_greater_or_equal 方法，用于查找跳表中键等于目标键（key）或者键是大于目标键的最小键所对应的节点。
    /// 如果目标键大于跳表中所有键，则返回 None。
    fn get_greater_or_equal<'a>(&'a self, key: &[u8]) -> Option<&'a Node> {
        // Start at the highest skip link of the head node, and work down from there
        // 从跳表的头节点（self.head）开始查找
        let mut current = self.head.as_ref() as *const Node;
        // 从跳表的最高层级（self.head.skips.len() - 1）开始向下遍历
        let mut level = self.head.skips.len() - 1;
        loop {
            unsafe {
                // 在当前层级检查当前节点的跳跃指针（skips[level]）指向的下一个节点
                if let Some(next) =(&(*current).skips)[level] {
                    // 使用比较器（self.cmp）比较下一个节点的键与目标键：
                    let ord = self.cmp.cmp(&(*next).key, key);
                    match ord {
                        // 如果下一个节点的键小于目标键（Ordering::Less）：移动到下一个节点，继续在当前层级查找
                        Ordering::Less => {
                            current = next;
                            continue;
                        }
                        // 如果下一个节点的键等于目标键（Ordering::Equal）：直接返回该节点
                        Ordering::Equal => return Some(&(*next)),
                        // 如果下一个节点的键大于目标键（Ordering::Greater）：
                        // 若已在最底层（level == 0），则返回该节点（它是大于目标键的最小节点）
                        // 否则降低层级（level -= 1），继续在更低层级查找
                        Ordering::Greater => {
                            if level == 0 {
                                return Some(&(*next));
                            }
                        }
                    }
                }
            }
            if level == 0 {
                break;
            }
            level -= 1;
        }

        unsafe {
            // 当遍历到最底层（level == 0）且循环结束后，检查当前节点是否符合条件
            // 如果当前节点是头节点或为空，或其键小于目标键，则返回 None, 否则返回当前节点
            if current.is_null() || current == self.head.as_ref() {
                None
            } else if self.cmp.cmp(&(*current).key, key) == Ordering::Less {
                None
            } else {
                Some(&(*current))
            }
        }
    }

    /// Finds the node immediately before the node with key.
    /// Returns None if no smaller key was found.
    ///
    /// 这段代码定义了 get_next_smaller 方法，用于在跳表（Skip List） 中查找键值小于指定键（key）的最大节点，即 “紧挨着目标 key 的前一个节点”。
    /// 如果不存在这样的节点（如所有节点的键都大于等于key），则返回None。
    ///
    ///
    fn get_next_smaller<'a>(&'a self, key: &[u8]) -> Option<&'a Node> {
        // Start at the highest skip link of the head node, and work down from there
        let mut current = self.head.as_ref() as *const Node;
        // 从跳表的头节点（self.head）开始查找，初始层级设为头节点最高的跳跃指针层级（self.head.skips.len() - 1）。
        let mut level = self.head.skips.len() - 1;

        loop {
            // 使用原始指针（*const Node）操作以提高性能（需注意unsafe块的使用）。
            unsafe {
                // 在当前层级中，检查当前节点的跳跃指针（next）指向的节点：
                if let Some(next) = (&(*current).skips)[level] {
                    let ord = self.cmp.cmp(&(*next).key, key);
                    // 若next节点的键小于目标键（Ordering::Less），则移动到next节点（利用高层级指针快速前进）。
                    // 若next节点的键大于等于目标键，则不移动，尝试降低层级继续查找。
                    if let Ordering::Less = ord {
                        current = next;
                        continue;
                    }
                }
            }
            // 当当前层级为 0（最底层，包含所有节点）时，退出循环。
            if level == 0 {
                break;
            }
            level -= 1;
        }

        // 循环结束后，current指向的节点是 “小于目标键的最大节点” 候选：
        // 若current是空指针或仍指向头节点，说明没有符合条件的节点，返回None。
        // 若current节点的键不小于目标键（异常情况），返回None。
        // 否则，返回current节点的引用（Some(&(*current))）。
        unsafe {
            if current.is_null() || current == self.head.as_ref() {
                // If we're past the end for some reason or at the head
                None
            } else if self.cmp.cmp(&(*current).key, key) != Ordering::Less {
                None
            } else {
                Some(&(*current))
            }
        }
    }

    /// 这段代码定义了跳表（Skip List）的 insert 方法，用于向跳表中插入新的键值对，同时维持跳表的有序性和层级结构。跳表是一种高效的有序数据结构，支持平均 O (log n) 时间复杂度的插入、删除和查找操作。
    fn insert(&mut self, key: Vec<u8>, val: Vec<u8>) {
        assert!(!key.is_empty());

        // Keeping track of skip entries that will need to be updated
        // 创建 prevs 数组，用于记录新节点在各层级上的前驱节点（即插入位置的前一个节点）。
        let mut prevs: [Option<*mut Node>; MAX_HEIGHT] = [None; MAX_HEIGHT];
        // 通过 random_height() 为新节点随机生成一个层级高度（new_height），这是跳表实现高效查找的关键（高层级节点可跳过更多元素）。
        let new_height = self.random_height();
        let prevs = &mut prevs[0..new_height];
        // 从跳表的最高层级开始遍历（level = MAX_HEIGHT - 1），从头部节点（self.head）出发。
        let mut level = MAX_HEIGHT - 1;
        let mut current = self.head.as_mut() as *mut Node;
        // Set previous node for all levels to current node.
        (0..prevs.len()).for_each(|i| {
            prevs[i] = Some(current);
        });

        // Find the node after which we want to insert the new node; this is the node with the key
        // immediately smaller than the key to be inserted.
        loop {
            // 对每个层级：
            // 如果当前节点的下一个节点（next）的键小于目标键，则移动到下一个节点。
            // 否则，记录当前节点作为该层级的前驱节点（prevs[level]），并降低层级继续查找。
            // 当遍历到最底层（level = 0）时，找到最终插入位置（所有节点按键有序排列）。
            unsafe {
                if let Some(next) = (&(*current).skips)[level] {
                    // If the wanted position is after the current node
                    let ord = self.cmp.cmp(&(*next).key, &key);

                    assert!(ord != Ordering::Equal, "No duplicates allowed");

                    if ord == Ordering::Less {
                        current = next;
                        continue;
                    }
                }
            }

            if level < new_height {
                prevs[level] = Some(current);
            }

            if level == 0 {
                break;
            } else {
                level -= 1;
            }
        }

        // Construct new node
        // 构建新节点（Node），包含键、值和对应层级的跳跃指针（skips）。
        // 对新节点的每个层级，更新前驱节点的跳跃指针：将前驱节点的指针指向新节点，新节点的指针指向原前驱节点的下一个节点（类似链表插入操作，但需处理多个层级）。
        let mut new_skips = Vec::new();
        new_skips.resize(new_height, None);
        let mut new = Box::new(Node {
            skips: new_skips,
            next: None,
            key: key.into(),
            value: val.into(),
        });
        let newp = new.as_mut() as *mut Node;

        (0..new_height).for_each(|i| {
            if let Some(prev) = prevs[i] {
                unsafe {
                    new.skips[i] = (&(*prev).skips)[i];
                    (&mut (*prev).skips)[i] = Some(newp);
                }
            }
        });
        // 更新跳表的内存占用估算（approx_mem）和节点总数（len）。
        // 处理最底层的普通链表指针（next），确保基础链表结构正确。
        let added_mem = size_of::<Node>()
            + size_of::<Option<*mut Node>>() * new.skips.len()
            + new.key.len()
            + new.value.len();
        self.approx_mem += added_mem;
        self.len += 1;

        // Insert new node by first replacing the previous element's next field with None and
        // assigning its value to new.next...
        new.next = unsafe { (*current).next.take() };
        // ...and then setting the previous element's next field to the new node
        unsafe {
            let _ = replace(&mut (*current).next, Some(new));
        };
    }
    /// Runs through the skipmap and prints everything including addresses
    ///
    /// 这段代码定义了 dbg_print 方法，用于调试目的打印跳表（Skip List）中的所有节点信息，包括节点地址、键值对以及各层级的跳跃指针（skips），帮助开发者观察和验证跳表的结构是否正确。
    ///
    /// 这个方法的典型用途是：
    ///
    /// 验证插入、删除操作后跳表的结构是否符合预期（如指针是否正确更新、节点顺序是否保持有序）。
    ///
    /// 排查跳表操作中的逻辑错误（如指针断裂、层级混乱等问题）。
    ///
    /// 简单来说，它是跳表的 “结构调试打印器”，通过输出详细的节点信息和指针关系，帮助开发者理解和验证跳表的内部状态。
    fn dbg_print(&self) {
        // 从跳表的头节点（self.head）开始，用原始指针（*const Node）跟踪当前节点（current）。
        let mut current = self.head.as_ref() as *const Node;
        loop {
            unsafe {
                // 对于每个节点，打印其内存地址（current）、键（(*current).key）、值（(*current).value）以及各层级的跳跃指针（(*current).skips）。
                // 这些信息能直观展示节点的存储内容和指针指向关系，方便调试时检查跳表结构。
                eprintln!(
                    "{:?} {:?}/{:?} - {:?}",
                    current,
                    (*current).key,
                    (*current).value,
                    (*current).skips
                );
                // 通过最底层（level=0）的跳跃指针（(&(*current).skips)[0]）依次访问所有节点（因为跳表的最底层包含所有节点，形成完整链表），直到遇到 None（表尾）时停止。
                if let Some(next) = (&(*current).skips)[0] {
                    current = next;
                } else {
                    break;
                }
            }
        }
    }
}

/// 这段代码定义了一个名为 SkipMapIter 的公共结构体，它是跳表（SkipMap）的迭代器类型，用于遍历跳表中的元素。
pub struct SkipMapIter {
    /// 通过 Rc（引用计数）和 RefCell（内部可变性）持有对跳表内部实现 InnerSkipMap 的引用，这使得迭代器能访问跳表的数据，同时允许多个迭代器共享同一个跳表实例
    map: Rc<RefCell<InnerSkipMap>>,
    /// 一个原始指针，指向当前迭代到的跳表节点（Node），用于跟踪迭代位置
    current: *const Node,
}

impl LdbIterator for SkipMapIter {
    fn advance(&mut self) -> bool {
        println!("----------skip map advance----------");
        // we first go to the next element, then return that -- in order to skip the head node
        let r = unsafe {
            (*self.current)
                .next
                .as_ref()
                .map(|next| {
                    self.current = next.as_ref() as *const Node;
                    true
                })
                .unwrap_or(false)
        };
        if !r {
            self.reset();
        }
        r
    }
    /// 这段代码定义了 SkipMapIter 迭代器的 reset 方法，用于将迭代器重置到初始状态。
    ///
    /// 方法通过 self.map.borrow().head.as_ref() 获取跳表的头节点（head）的引用
    ///
    /// 然后将迭代器的 current 指针设置为这个头节点，使迭代器回到起始位置
    fn reset(&mut self) {
        println!("----------skip map reset----------");
        self.current = self.map.borrow().head.as_ref();
    }

    /// 这段代码定义了 SkipMapIter 迭代器的 seek 方法，用于将迭代器定位到跳表中大于或等于目标键（key） 的第一个节点位置。
    fn seek(&mut self, key: &[u8]) {
        println!("----------skip map seek----------");
        // 调用跳表内部实现的 get_greater_or_equal(key) 方法，在跳表中查找键值大于或等于 key 的第一个节点
        // 这个方法利用跳表的高效查找特性（通过多层指针快速定位），避免了从头开始遍历的低效性
        if let Some(node) = self.map.borrow().get_greater_or_equal(key) {
            // 如果值不为空, 则说明找到了, 找到之后直接修改当前节点指针
            self.current = node as *const Node;
            return;
        }
        self.reset();
    }

    /// 这段代码定义了 SkipMapIter 迭代器的 valid 方法，用于判断迭代器当前是否处于有效状态（即是否指向一个包含实际数据的节点）。
    ///
    /// 方法通过比较迭代器的 current 指针（当前指向的节点）与跳表的头节点（self.map.borrow().head.as_ref()）来判断有效性
    ///
    /// 如果 current 不等于头节点，则返回 true（有效状态）
    ///
    /// 如果 current 等于头节点，则返回 false（无效状态）
    fn valid(&self) -> bool {
        println!("----------skip map valid----------");
        self.current != self.map.borrow().head.as_ref()
    }

    /// 这段代码定义了 SkipMapIter 迭代器的 current 方法，用于获取当前迭代位置节点中存储的键值对。
    fn current(&self) -> Option<(Bytes, Bytes)> {
        println!("----------skip map current----------");
        // 首先调用 self.valid() 检查当前迭代器是否处于有效状态（即 current 指针是否指向一个有效的节点）
        // 如果无效（例如迭代已结束或未指向任何节点），直接返回 None
        if self.valid() {
            // 若有效，则通过 unsafe 块操作原始指针 self.current（因为涉及原始指针解引用，需要显式标记为不安全操作）
            // 解引用当前节点指针 (*self.current，获取节点中存储的 key 和 value
            // 使用 Bytes::copy_from_slice 从节点的键和值中复制数据，创建新的 Bytes 实例（Bytes 通常是一种高效的字节容器类型）
            // 将键值对包装在 Some 中返回
            unsafe {
                println!("&(*self.current).key {:?}", &(*self.current).key);
                println!("&(*self.current).value {:?}", &(*self.current).value);
                Some((
                    Bytes::copy_from_slice(&(*self.current).key),
                    Bytes::copy_from_slice(&(*self.current).value),
                ))
            }
        } else {
            None
        }
    }
    fn prev(&mut self) -> bool {
        println!("----------skip map prev----------");
        // Going after the original implementation here; we just seek to the node before current().
        if self.valid() {
            if let Some(prev) = self
                .map
                .borrow()
                .get_next_smaller(unsafe { &(*self.current).key })
            {
                self.current = prev as *const Node;
                if !prev.key.is_empty() {
                    return true;
                }
            }
        }
        self.reset();
        false
    }
}

#[cfg(test)]
pub mod tests {
    use super::*;
    use crate::cmp::MemtableKeyCmp;
    use crate::options;
    use crate::test_util::{test_iterator_properties, LdbIteratorIter};
    use crate::types::current_key_val;

    pub fn make_skipmap() -> SkipMap {
        let mut skm = SkipMap::new(options::for_test().cmp);
        let keys = vec![
            "aba", "abb", "abc", "abd", "abe", "abf", "abg", "abh", "abi", "abj", "abk", "abl",
            "abm", "abn", "abo", "abp", "abq", "abr", "abs", "abt", "abu", "abv", "abw", "abx",
            "aby", "abz",
        ];

        for k in keys {
            skm.insert(k.as_bytes().to_vec(), "def".as_bytes().to_vec());
        }
        skm
    }

    #[test]
    fn test_insert() {
        let skm = make_skipmap();
        assert_eq!(skm.len(), 26);
        skm.map.borrow().dbg_print();
    }

    #[test]
    #[should_panic]
    fn test_no_dupes() {
        let mut skm = make_skipmap();
        // this should panic
        skm.insert("abc".as_bytes().to_vec(), "def".as_bytes().to_vec());
        skm.insert("abf".as_bytes().to_vec(), "def".as_bytes().to_vec());
    }

    #[test]
    fn test_contains() {
        let skm = make_skipmap();
        assert!(skm.contains(b"aby"));
        assert!(skm.contains(b"abc"));
        assert!(skm.contains(b"abz"));
        assert!(!skm.contains(b"ab{"));
        assert!(!skm.contains(b"123"));
        assert!(!skm.contains(b"aaa"));
        assert!(!skm.contains(b"456"));
    }

    #[test]
    fn test_find() {
        let skm = make_skipmap();
        assert_eq!(
            &*skm.map.borrow().get_greater_or_equal(b"abf").unwrap().key,
            b"abf"
        );
        assert!(skm.map.borrow().get_greater_or_equal(b"ab{").is_none());
        assert_eq!(
            &*skm.map.borrow().get_greater_or_equal(b"aaa").unwrap().key,
            b"aba"
        );
        assert_eq!(
            &*skm.map.borrow().get_greater_or_equal(b"ab").unwrap().key,
            b"aba"
        );
        assert_eq!(
            &*skm.map.borrow().get_greater_or_equal(b"abc").unwrap().key,
            b"abc"
        );
        assert!(skm.map.borrow().get_next_smaller(b"ab0").is_none());
        assert_eq!(
            &*skm.map.borrow().get_next_smaller(b"abd").unwrap().key,
            b"abc"
        );
        assert_eq!(
            &*skm.map.borrow().get_next_smaller(b"ab{").unwrap().key,
            b"abz"
        );
    }

    #[test]
    fn test_empty_skipmap_find_memtable_cmp() {
        // Regression test: Make sure comparator isn't called with empty key.
        let cmp: Rc<Box<dyn Cmp>> = Rc::new(Box::new(MemtableKeyCmp(options::for_test().cmp)));
        let skm = SkipMap::new(cmp);

        let mut it = skm.iter();
        it.seek(b"abc");
        assert!(!it.valid());
    }

    #[test]
    fn test_skipmap_iterator_0() {
        let skm = SkipMap::new(options::for_test().cmp);
        let mut i = 0;

        for (_, _) in LdbIteratorIter::wrap(&mut skm.iter()) {
            i += 1;
        }

        assert_eq!(i, 0);
        assert!(!skm.iter().valid());
    }

    #[test]
    fn test_skipmap_iterator_init() {
        let skm = make_skipmap();
        let mut iter = skm.iter();

        assert!(!iter.valid());
        iter.next();
        assert!(iter.valid());
        iter.reset();
        assert!(!iter.valid());

        iter.next();
        assert!(iter.valid());
        iter.prev();
        assert!(!iter.valid());
    }

    #[test]
    fn test_skipmap_iterator() {
        let skm = make_skipmap();
        let mut i = 0;

        for (k, v) in LdbIteratorIter::wrap(&mut skm.iter()) {
            assert!(!k.is_empty());
            assert!(!v.is_empty());
            i += 1;
        }
        assert_eq!(i, 26);
    }

    #[test]
    fn test_skipmap_iterator_seek_valid() {
        let skm = make_skipmap();
        let mut iter = skm.iter();

        iter.next();
        assert!(iter.valid());
        assert_eq!(current_key_val(&iter).unwrap().0, "aba".as_bytes().to_vec());
        iter.seek(b"abz");
        assert_eq!(
            current_key_val(&iter).unwrap(),
            ("abz".as_bytes().to_vec(), "def".as_bytes().to_vec())
        );
        // go back to beginning
        iter.seek(b"aba");
        assert_eq!(
            current_key_val(&iter).unwrap(),
            (b"aba".to_vec(), b"def".to_vec())
        );

        iter.seek(b"");
        assert!(iter.valid());
        iter.prev();
        assert!(!iter.valid());

        while iter.advance() {}
        assert!(!iter.valid());
        assert!(!iter.prev());
        assert_eq!(current_key_val(&iter), None);
    }

    #[test]
    fn test_skipmap_behavior() {
        let mut skm = SkipMap::new(options::for_test().cmp);
        let keys = vec!["aba", "abb", "abc", "abd"];
        for k in keys {
            skm.insert(k.as_bytes().to_vec(), "def".as_bytes().to_vec());
        }
        test_iterator_properties(skm.iter());
    }

    #[test]
    fn test_skipmap_iterator_prev() {
        let skm = make_skipmap();
        let mut iter = skm.iter();

        iter.next();
        assert!(iter.valid());
        iter.prev();
        assert!(!iter.valid());
        iter.seek(b"abc");
        iter.prev();
        assert_eq!(
            current_key_val(&iter).unwrap(),
            ("abb".as_bytes().to_vec(), "def".as_bytes().to_vec())
        );
    }

    #[test]
    fn test_skipmap_iterator_concurrent_insert() {
        time_test!();
        // Asserts that the map can be mutated while an iterator exists; this is intentional.
        let mut skm = make_skipmap();
        let mut iter = skm.iter();

        assert!(iter.advance());
        skm.insert("abccc".as_bytes().to_vec(), "defff".as_bytes().to_vec());
        // Assert that value inserted after obtaining iterator is present.
        for (k, _) in LdbIteratorIter::wrap(&mut iter) {
            if k == "abccc".as_bytes() {
                return;
            }
        }
        panic!("abccc not found in map.");
    }
}
